import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.*;
import java.util.stream.Stream;

/**
 * 四数之和
 * 题目：给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [-1,  0, 0, 1],
 * [-2, -1, 1, 2],
 * [-2,  0, 0, 2]
 * ]
 * <p>
 * 来源：力扣（LeetCode-18）
 * 链接：https://leetcode-cn.com/problems/4sum
 *
 * @author godfrey
 * @since 2020-11-03
 */
@DisplayName("四数之和")
public class FourSum extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments(new int[]{1, 0, -1, 0, -2, 2}, 0),
                Arguments.arguments(new int[]{0, 0, 0, 0}, 0)
        );
    }

    @DisplayName("降维，先排序，后夹逼(双指针)-时间复杂度O(n^3)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void fourSum(int[] nums, final int target) {
        final int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len < 4) {
            System.out.println(res);
            return;
        }
        Arrays.sort(nums);
        int l, r, sum;
        for (int i = 0; i < len - 3; ++i) {
            //重复元素num[i]
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; ++j) {
                //重复元素num[j]
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                l = j + 1;
                r = len - 1;
                while (l < r) {
                    sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum < target) {
                        ++l;
                        //重复元素num[l]
                        while (l < r && nums[l] == nums[l - 1]) {
                            ++l;
                        }
                    } else if (sum > target) {
                        --r;
                        //重复元素num[r]
                        while (l < r && nums[r] == nums[r + 1]) {
                            --r;
                        }
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        ++l;
                        --r;
                        //重复元素num[l]
                        while (l < r && nums[l] == nums[l - 1]) {
                            ++l;
                        }
                        //重复元素num[r]
                        while (l < r && nums[r] == nums[r + 1]) {
                            --r;
                        }
                    }
                }
            }
        }
        System.out.println(res);
    }


    @DisplayName("双指针优化-时间复杂度O(n^3)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void fourSum2(int[] nums, final int target) {
        final int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len < 4) {
            System.out.println(res);
            return;
        }
        Arrays.sort(nums);
        int l, r, sum, min1, max1, min, max;
        for (int i = 0; i < len - 3; ++i) {
            //重复元素num[i]
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏
            min1 = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
            if (min1 > target) {
                break;
            }
            //获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略
            max1 = nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1];
            if (max1 < target) {
                continue;
            }
            for (int j = i + 1; j < len - 2; ++j) {
                //重复元素num[j]
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                l = j + 1;
                r = len - 1;
                //获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏
                min = nums[i] + nums[j] + nums[j + 1] + nums[j + 2];
                if (min > target) {
                    break;
                }
                //获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略
                max = nums[i] + nums[j] + nums[len - 2] + nums[len - 1];
                if (max < target) {
                    continue;
                }
                while (l < r) {
                    sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum < target) {
                        ++l;
                        //重复元素num[l]
                        while (l < r && nums[l] == nums[l - 1]) {
                            ++l;
                        }
                    } else if (sum > target) {
                        --r;
                        //重复元素num[r]
                        while (l < r && nums[r] == nums[r + 1]) {
                            --r;
                        }
                    } else {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        ++l;
                        --r;
                        //重复元素num[l]
                        while (l < r && nums[l] == nums[l - 1]) {
                            ++l;
                        }
                        //重复元素num[r]
                        while (l < r && nums[r] == nums[r + 1]) {
                            --r;
                        }
                    }
                }
            }

        }
        System.out.println(res);
    }

    @DisplayName("哈希表做缓存-时间复杂度O(n^2)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void fourSum3(int[] nums, final int target) {
        final int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len < 4) {
            System.out.println(res);
            return;
        }
        Arrays.sort(nums);
        final Map<Integer, List<int[]>> cache = new HashMap<>();
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                List<int[]> value = cache.computeIfAbsent(nums[i] + nums[j], k -> new ArrayList<>());
                value.add(new int[]{i, j});
            }
        }
        final Set<String> used = new HashSet<>();
        for (int i = 0; i < len - 1; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                final List<int[]> list = cache.get(target - nums[i] - nums[j]);
                if (list == null) {
                    continue;
                }
                for (int[] pair : list) {
                    if (j >= pair[0]) {
                        continue;  // 去重
                    }
                    final Integer[] sol = new Integer[]{nums[i], nums[j], nums[pair[0]], nums[pair[1]]};
                    Arrays.sort(sol);
                    final String key = Arrays.toString(sol);
                    if (!used.contains(key)) {
                        res.add(Arrays.asList(sol));
                        used.add(key);
                    }
                }
            }

        }
        System.out.println(res);
    }
}
